package org.example.sort.type;

import java.util.Comparator;

/**
 * 类描述：提前终止优化
 * <br>
 *
 * @author ZS
 * @version 1.0
 * @date 2020/12/28
 **/
public class BubbleSort2<E> extends AbstractSort<E> {
    public BubbleSort2() {
        super();
    }

    public BubbleSort2(Comparator<E> comparator) {
        super(comparator);
    }

    @Override
    protected E[] sort() {
        // 如果一趟扫描没有元素交换，则说明已经完全有序，可以终止循环
        // 该改进只适合数组中元素有序较多的情况，否则会比原始版本慢
        boolean swap = false;
        for (int end = elements.length - 1; end > 0; end--) {
            swap = false;
            for (int j = 1; j <= end; j++) {
                if (compare(elements[j - 1], elements[j]) > 0) {
                    swap(j - 1, j);
                    swap = true;
                }
            }
            // 未进行过交换，说明完全有序
            if (!swap) {
                break;
            }
        }
        return elements;
    }
}
